package leetcode

import (
	"gitee.com/ombak/leetcode/pkg/list"
)

// https://leetcode.com/problems/linked-list-cycle-ii/
func detectCycle(head *list.ListNode) *list.ListNode {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			break
		}
	}
	// no cycle
	if fast == nil || fast.Next == nil {

		return nil
	}
	// cycle collision point
	collision := head
	for collision != fast {
		fast = fast.Next
		collision = collision.Next
	}
	return collision
}
